package com.rui.study.algorithm.P_八皇后;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-12-28 16:25
 **/
public class Solution20181228 {

    private static final int DEFAULT_N = 8;
    private int n;

    private int[] board;

    private int resolvedCount = 1;

    public Solution20181228() {
        this(DEFAULT_N);
    }

    public Solution20181228(int n) {
        this.n = n;
        this.board = new int[n];
    }

    public void call8Queue(int row) {

        if (row == n) {
            System.out.println("--------\r\n" + n + "皇后解法-" + resolvedCount++);
            printBoard(board);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isOK(row, col)) {                   // 尝试在每一列放皇后
                board[row] = col;
                call8Queue(row + 1);
            }
        }
    }

    private boolean isOK(int row, int col) {
        int leftUp = col - 1, rigthUp = col + 1;
        for (int i = row - 1; i >= 0; i--) {        // 向上逐行检查
            if (board[i] == col) return false;      // 检查同一列有没有皇后
            if (leftUp >= 0) {
                if (board[i] == leftUp) return false;   // 检查左上角对角线
            }
            if (rigthUp < n) {
                if (board[i] == rigthUp) return false;  // 检查右上角对角线
            }
            leftUp--;
            rigthUp++;
        }
        return true;
    }


    private void printBoard(int[] board) {
        int length = board.length;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (board[i] == j) {
                    System.out.print("Q");
                }else {
                    System.out.print("*");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Solution20181228 solution = new Solution20181228(12);
        solution.call8Queue(0);
//        int[] board = {0,1,2,3,4};
//        solution.printBoard(board);
    }
}
